// 给出一个无重叠的 ，按照区间起始端点排序的区间列表。
// 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

const insert = function (intervals: number[][], newInterval: number[]): number[][] {
    const res: number[][] = []; // 结果数组
    let beyond: boolean = false;// 标记变量，判断目前原区间集合是否有迈过重叠区间
    for (let interval of intervals) {
        // 最简单的情况，无重叠，现区间在新区间的左边
        if (interval[1] < newInterval[0]) {
            res.push(interval);
            // 第二简单的情况，无重叠，现区间在新区间右边
        } else if (interval[0] > newInterval[1]) {
            if (beyond == false) {// 为了保证结果区间有序，第一次插入右侧重叠区间时应该插入新区间
                beyond = true;// 标记变量表示已经越过重叠区间
                res.push(newInterval);
            }
            res.push(interval);
        } else if (beyond === false) {// 最复杂的情况，我们只需要保证标记变量为false即可
            newInterval[0] = Math.min(interval[0], newInterval[0]);
            newInterval[1] = Math.max(interval[1], newInterval[1]);
        }
    }
    // 特殊情况，整个数组都位于给定区间内
    if (beyond === false) {
        beyond = true;
        res.push(newInterval);
    }
    return res;
};

insert([
    [1, 3],
    [6, 9]
], [2, 5])



// 这道题目实际上是一道外强中干的题目，难度其实主要在于数学，
// 即分类讨论的思想上
// 我们思考，对于一个给定的区间，原区间集中的区间有哪几种情况
// 1.目前区间全部位于给定区间的左侧，无重叠，这种很好想，直接加入结果数组中就行了
// 2.目前区间全部位于给定区间的右侧，无重叠，这种就要思考一下了，因为插入的时机不好确定（需要保证结果区间仍然有序）
// 3.最复杂的情况，即出现重叠，可能性又很多，但唯一可以确定的是合并后的区间中
// 左区间为原区间和给定区间的左侧最小值，右区间为原区间和给定区间的右侧最大值
// 因为原区间集给定的就是有序的，我们可以把整个遍历过程分为三部分
// 无重叠左区间->有重叠区间->无重叠右区间
// 我们使用1个标记变量用来表示当前遍历是否已经迈过了有重叠区间，然后在2、3中加入if判断即可
// 最后要考虑一种特殊情况，即整个数组都位于给定区间内
// 这种情况下在返回结果前要注意加入合并后的给定区间